/**
 * @file   HashTable.h
 * @author zhang-zh
 * @date   2020.12.13 Sunday
 * 
 * @brief  A headfile for a hash table. The table is used to
 *         count the number of different words.
 * 
 */

#ifndef __zhang_hashtable__
#define __zhang_hashtable__
#define HASHSIZE 64

#include <iostream>
#include <cstring>
#include <string>

using std::string;

class Node
{
public:
    string key;
    int value;
    Node* next;
    int mark;
public:
    Node()
    {
        key = "";
        value = 0;
        next = NULL;
        mark = 0;
    };
    ~Node(){};
    Node(string _key)
    {
        key = _key;
        value = 1;
        next = NULL;
        mark = 0;
    };
};

class HashTable
{
public:
    Node* node[HASHSIZE];
public:
    HashTable();
    ~HashTable(){};
    void insert(string _key);
    size_t hash(string _key);
    Node* search(string _key);
    void display();
    void displayall();
};

HashTable::HashTable()
{
    for(int i = 0; i < HASHSIZE; i++)
    {
        node[i] = NULL;
    }
}

Node* HashTable::search(string _key)
{
    Node* _x;
    size_t index;
    index = hash(_key);
    _x = node[index];
    while(_x != NULL)
    {
        if(_key == _x->key)
        return _x;
        _x = _x->next;
    }
    return NULL;
}

void HashTable::insert(string _key)
{
    Node* _x = search(_key);
    size_t index = hash(_key);
    if(_x == NULL)
    {
        Node* _y = new Node(_key);
        _y->next = node[index];
        node[index] = _y;
    }
    else
    {
        _x->value += 1;
    }
}

size_t HashTable::hash(string _key)
{
    size_t hash=0;
    for(unsigned int i = 0; i<_key.size(); i++)
    {
        hash += (hash << 5) + _key[i];
    }
    
    return hash & 63;
///    size_t hash = 0;
///    while (*_key)
///    {
///        hash += (*_key++);
///    }
///    return hash&63;
}

void HashTable::display()
{
    Node* x = new Node;
    for(int i = 0; i<HASHSIZE; i++)
    {
        Node* y = node[i];
        while(y != NULL)
        {
            if(y->mark == 0 && x->value < y->value)
            {
                x = y;
            }
            y = y->next;
        }
    }
    x->mark = 1;
    std::cout << "Word: " << x->key <<"  Number: "<< x->value << std::endl;
}

void HashTable::displayall()
{
    for(int i=0; i<HASHSIZE; i++)
    {
        Node* y = node[i];
        while(y != NULL)
        {
            std::cout << "Word: " << y->key <<"  Number: "<< y->value << std::endl;
            y = y->next;
        }
    }
}

#endif